7package LeetCode.interview;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._083_Remove_Duplicates_from_Sorted_List.ListNode;
import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.launcher.resources.launcher;
import sun.tools.jar.resources.jar;
import util.LogUtils;
import 算法.排序.归并排序.MergeSortTest1;
import 算法.排序.快速排序.QuickSort;

/*
 * 
原题　
		Given a linked list, swap every two adjacent nodes and return its head.
	
	For example,
	Given 1->2->3->4, you should return the list as 2->1->4->3.
	
	Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
	


题目大意
	
	TODO:需要再思考一下
解题思路
	//参考
	http://www.cnblogs.com/springfor/p/3862030.html
	
 * @Date 2017-09-17 11：33
 */
public class _024_Swap_Nodes_in_Pairs {
	public class ListNode {
	    int val;
	    ListNode next;
	    ListNode()	 	{}
	    ListNode(int x) { val = x; }
}
    public ListNode swapPairs(ListNode head) {
    	//在链表前加一个临时节点
    	ListNode fakeNode = new ListNode(-1);
    	fakeNode.next = head;
    	ListNode ptr1 = fakeNode, ptr2 = head;	
    	/*
     		当链表长度为奇数时，ptr2.next可能为null；
 			当链表长度为偶数时，ptr2可能为null。
			所以把这两个情况作为终止条件，在while判断就好，最后返回fakehead.next。
    	 */
		//nextStart指向要交换的两个节点的前一个节点;
    	while (ptr2!=null && ptr2.next!=null) {
    		ListNode nextStart = ptr2.next.next;
    		ptr2.next.next = ptr2;
    		ptr1.next = ptr2.next;
    		ptr2.next = nextStart;
    		ptr1 = ptr2;
    		ptr2 = ptr2.next;
    	}
    	traverse(fakeNode.next);
		return fakeNode.next;		//取出临时节点
    }
    
	private ListNode newLinkList1() {
		ListNode root = new ListNode(1);
		root.next = new ListNode(1);
		root.next.next = new ListNode(2);
		root.next.next.next = new ListNode(3);
		root.next.next.next.next = new ListNode(4);
		return root;
	}
	private void traverse(ListNode l) {
		while (l != null) {
			System.out.println(l.val+">>");
			l = l.next;
		}
	}
	
	
	
    public static void main(String[] args) {
		_024_Swap_Nodes_in_Pairs obj = new _024_Swap_Nodes_in_Pairs();
//		obj.twoSum(new int[]{1, 2, 3, 4, 5, 6, 7}, 7);
//		obj.twoSum2(new int[]{2, 7, 11, 15}, 9);
		LogUtils.println("结果", obj.swapPairs(obj.newLinkList1()));

	}

}
